import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 30. 串联所有单词的子串
 * https://leetcode.cn/problems/substring-with-concatenation-of-all-words
 */
class SubstringWithConcatenationOfAllWords {


    /**
     * 方法：findSubstring
     *
     * 逻辑:
     * 1. 初始化结果列表 `ans` 和单词频率表 `map`，统计 `words` 中每个单词的出现次数。
     * 2. 计算每个单词的长度 `wordSize` 和单词的数量 `wordNum`。
     * 3. 使用滑动窗口技术遍历字符串 `s`，窗口大小为 `wordSize`，从 0 到 `wordSize - 1` 开始遍历。
     * 4. 对于每一个起始位置 `i`，使用两个指针 `left` 和 `right` 来表示当前窗口的左右边界，并初始化计数器 `wordCnt` 和临时频率表 `tmp_map`。
     * 5. 在窗口内逐个检查子串 `w` 是否在 `map` 中：
     *    - 如果不在，则重置窗口和计数器。
     *    - 如果在，则更新 `tmp_map` 和 `wordCnt`，并检查是否超出频率限制，调整左边界以保持窗口有效。
     * 6. 如果窗口内的单词数量等于 `wordNum`，将左边界 `left` 加入结果列表 `ans`。
     * 7. 返回所有匹配成功的起始索引。
     *
     * Args:
     * - s (String): 输入字符串。
     * - words (String[]): 单词数组。
     *
     * Returns:
     * - List<Integer>: 包含所有由 `words` 组成的子串在 `s` 中的起始索引。
     *
     * Time:
     * - O(n * m)，其中 n 是字符串 `s` 的长度，m 是单词数组 `words` 的长度。对于每一个起始位置 `i`，最坏情况下需要遍历所有单词。
     *
     * Space:
     * - O(m)，用于存储单词频率表 `map` 和当前窗口的单词频率表 `tmp_map‘
     *
     */
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) return ans;
        HashMap<String, Integer> map = new HashMap<>();
        for(String word : words){
            ////统计每个单词出现次数
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        int wordSize = words[0].length();
        int wordNum = words.length;
        for(int i = 0; i < wordSize; i++){
            int left = i, right = i, wordCnt = 0;
            //存储窗口中单词
            HashMap<String, Integer> tmp_map = new HashMap<>();
            while(right + wordSize <= s.length()){
                String w = s.substring(right, right + wordSize);
                right += wordSize;
                if(!map.containsKey(w)){
                    wordCnt = 0;
                    left = right; //无匹配窗口向右滑动
                    tmp_map.clear();
                } else {
                    tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1);
                    wordCnt++;
                    while (tmp_map.getOrDefault(w, 0) > map.getOrDefault(w, 0)){
                        String t_w= s.substring(left, left + wordSize);
                        wordCnt--;
                        tmp_map.put(t_w, tmp_map.getOrDefault(t_w, 0) - 1);
                        left += wordSize; ////左端点单词离开窗口
                    }
                    if(wordCnt == wordNum){
                        ans.add(left); // 左端点下标加入答案                        
                    }
                }
            }
        }

        return ans;
    }
}